#include "../seqlist.h"

/**
 * 二分查找的非递归实现算法
 * @param {seqlist}     l       顺序表
 * @param {datatype}    key     要查找的关键字
 * @return {int}                查找成功返回关键字在顺序表中的位置，否则返回-1
 */
int binsearch1(seqlist l,datatype key) {
    int low = 0, high = l.len - 1, mid;
    while (low <= high)
    {
       mid = (low + high) / 2;
       if(l.data[mid] == key) return mid;  // 查找成功
       else if(l.data[mid] > key) high = mid - 1;  // 继续在前半部分查找
       else low = mid + 1;  // 继续在后半部分查找
    }
    
    return -1;  // 查找失败
}

/**
 * 二分查找的递归实现算法
 * @param {seqlist}     l       顺序表
 * @param {datatype}    key     要查找的关键字
 * @param {int}         low     顺序表的起始位置
 * @param {int}         high    顺序表的结束位置
 * @return {int}                查找成功返回关键字在顺序表中的位置，否则返回-1
 */
int binsearch2(seqlist l,datatype key,int low,int high) {
    int mid, k;
    if(low > high) return -1;  // 查找失败
    else {
        mid = (low + high) / 2;
        if(l.data[mid] == key) return mid;  // 查找成功
        else if(l.data[mid] > key) k = binsearch2(l, key, low, mid - 1);  // 继续在前半部分查找
        else k = binsearch2(l, key, mid + 1, high);  // 继续在后半部分查找
    }
}